import collections
class Solution(object):
    def isRectangleCover(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        n = len(rectangles)
        x0 = min([rectangles[i][0] for i in range(n)])
        y0 = min([rectangles[i][1] for i in range(n)])
        x1 = max([rectangles[i][2] for i in range(n)])
        y1 = max([rectangles[i][3] for i in range(n)])
        total = (y1 - y0) * (x1 - x0)
        c = 0
        for t in rectangles:
            c += (t[2] - t[0]) * (t[3] - t[1])
        if c != total:
            return False

        d = collections.defaultdict(int)
        for rec in rectangles:
            d[(rec[0], rec[1])] += 1
            d[(rec[0], rec[3])] += 1
            d[(rec[2], rec[1])] += 1
            d[(rec[2], rec[3])] += 1

        if d[(x0, y0)] == 1 and d[(x0, y1)] == 1 and d[(x1, y0)] == 1 and d[(x1, y1)] == 1:
            d.pop((x0, y0))
            d.pop((x0, y1))
            d.pop((x1, y0))
            d.pop((x1, y1))
            for key in d:
                if d[key] == 1 or d[key] == 3:
                    return False
            return True
        else:
            return False



data = Solution()
rectangles = [[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]]
print(data.isRectangleCover(rectangles))
rectangles = [[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4]]
print(data.isRectangleCover(rectangles))
rectangles = [[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]]
print(data.isRectangleCover(rectangles))
